[BZOJ1951]-古代猪文

数论

https://vjudge.net/problem/HYSBZ-1951

题意：给定整数 q, n($1 \leq q, n \leq 10^9$)，计算 $q^{\sum_{d | n} C_{n}^d} mod 999911659$ 。

数论经典题！出现了很多知识点，值得回顾！

若 q = 999911659, 则上式结果为 0. 否则，因为 999911659 是质数，所以 q, 999911659 互质。由欧拉定理的推论得：

因此，本题的关键是计算 $q^{\sum_{d | n} C_n^d mod 999911658} (mod 999911659)$

尝试分解质因数，可以发现 $999911658 = 2 3 4679 * 35617$ 。

我们可以枚举 n 的约数 d，然后运用 Lucas 定理求组合数 $C_n^d$ ，分别计算出 $\sum_{d | n} C_n^d$ 对 2, 3, 4679, 35617 四个质数的取模结果，记为 a1, a2, a3, a4。求组合数时，可以对于质数 p，预处理 p 以内的所有阶乘以及阶乘的模 p 乘法逆元，就能快速计算。

最后用中国剩余定理求解线性同余方程组：

再用快速幂求 $q^x$ 即可。

想了想还真是用了不少定理啊公式的！快速幂，Lucas 定理，扩展欧几里得，中国剩余定理，费马小定理求乘法逆元，惊叹❗️

CODE：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
using namespace std;

const int mod = 999911659, N = 1e5 + 5;
const int T[4] = {2, 3, 4679, 35617};
typedef long long ll;
ll Q, n, Fac[4][N], r[4];

ll quick_pow(ll a, ll b, ll c) {
    a %= c;
    ll ret = 1;
    for (; b; b >>= 1) {
        if (b & 1) ret = ret * a % c;
        a = a * a % c;
    } return ret;
}

ll C(ll n, ll m, ll p) {
    if (m < n) return 0;
    return (Fac[p][m] * quick_pow(Fac[p][n] * Fac[p][m - n], T[p] - 2, T[p])) % T[p];
}

ll Lucas(ll a, ll b, ll p) {
    if (b == 0) return 1;
    return C(a % T[p], b % T[p], p) * Lucas(a / T[p], b / T[p], p) % T[p];
}

ll exGcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    ll d = exGcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}

ll CRT() {
    ll M = 999911658, ans = 0;
    for (int i = 0; i < 4; i++) {
        ll x, y, Mi = M / T[i];
        exGcd(Mi, T[i], x, y);
        ans = (ans + Mi * x * r[i]) % M;
    }
    if (ans < 0) ans += M;
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> Q;
    if (Q == mod) {
        printf("0\n");
        return 0;
    }
    for (int i = 0; i < 4; i++) {
        Fac[i][0] = 1;
        for (int j = 1; j <= T[i]; j++) Fac[i][j] = Fac[i][j - 1] * j % T[i];
    }
    for (int i = 0; i < 4; i++) {
        for (int j = 1; j * j <= n; j++)
            if (n % j == 0) {
                r[i] = (r[i] + Lucas(j, n, i)) % T[i];
                if (j * j != n) r[i] = (r[i] + Lucas(n / j, n, i)) % T[i];
            }
    }
    printf("%lld\n", quick_pow(Q, CRT(), mod));
    return 0;
}